package leetcode_1001_1100;

import node.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_1028 {
    public static void main(String[] args) {
//        TreeNode x = recoverFromPreorder("1-401--349---90--88");
        TreeNode x = recoverFromPreorder("1-2--3--4-5--6--7");
        System.out.println(x);
    }
    private static TreeNode recoverFromPreorder(String traversal) {
        int index = 0, n = traversal.length();
        List<int[]> list = new ArrayList<>();
        while (index < n){
            int depth = 0;
            while (index < n && traversal.charAt(index) == '-'){
                depth++;
                index++;
            }
            StringBuilder sb = new StringBuilder();
            while (index < n && traversal.charAt(index) != '-'){
                sb.append(traversal.charAt(index));
                index++;
            }
            int num = Integer.parseInt(sb.toString());
            list.add(new int[]{depth, num});
        }
        return f(list, 0, list.size() - 1);
    }
    private static TreeNode f(List<int[]> list, int l, int r){
        TreeNode root = new TreeNode(list.get(l)[1]);
        if (l == r){
            return root;
        }
        int m = -1, t = list.get(l)[0] + 1;
        for (int i = l + 2; i <= r; i++) {
            if (list.get(i)[0] == t){
                m = i;
                break;
            }
        }
        if (m != -1){
            TreeNode left = f(list, l + 1, m - 1);
            TreeNode right = f(list, m, r);
            root.left = left;
            root.right = right;
        }else {
            root.left = f(list, l + 1, r);
        }
        return root;
    }
}
